package com.zyk.grate_offer.class10;

/**
 * @author zhangsan
 * @date 2021/5/30 11:16
 */
public class Code02_KInversePairsArray {

    // r: 当前第几个数字
    // c: 有c个逆序对
    // dp[r][c] : 有多少种可以排列的可能
    // abcd<5>  abc<5>d  ab<5>cd  a<5>bcd  <5>abcd
    public static int kInversePairs(int n, int k) {
        int[][] dp = new int[n+1][k+1];
        dp[0][0] = 1;
        for (int r = 1; r <= n; r++) {
            dp[r][0] = 1;
            for (int c = 1; c <= k; c++) {
                if(c < r) {
                    dp[r][c] = dp[r-1][c] + dp[r][c-1];
                }else {
                    dp[r][c] = dp[r-1][c] + dp[r][c-1] - dp[r-1][c-r];
                }
            }
        }
        return dp[n][k];
    }

    public static int kInversePairs2(int n, int k) {
        int mod = 1000000007;
        int[][] dp = new int[n+1][k+1];
        dp[0][0] = 1;
        for (int r = 1; r <= n; r++) {
            dp[r][0] = 1;
            for (int c = 1; c <= k; c++) {
                dp[r][c] = (dp[r-1][c] + dp[r][c-1]) % mod;
                if(c >= r) {
                    dp[r][c] = (dp[r][c] - dp[r-1][c-r] + mod) % mod;   // 剪完可能为负数, 在mod答案就不对了
                }
            }
        }
        return dp[n][k];
    }

    public static void main(String[] args) {
        System.out.println(kInversePairs(3, 1));
    }


}
